package com.lw.leetcode.arr.c;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * <p>
 * arr
 * c
 * 1402. 做菜顺序
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/17 15:06
 */
public class MaxSatisfaction {

    public static void main(String[] args) {
        MaxSatisfaction test = new MaxSatisfaction();

        // 35
        int[] arr = {-2, 5, -1, 0, 3, -3};

        // 35
//        int[] arr = {-1,-8,0,5,-9};
        int i = test.maxSatisfaction(arr);
        System.out.println(i);
    }

    public int maxSatisfaction(int[] satisfaction) {
        Arrays.sort(satisfaction);
        int length = satisfaction.length;
        int end = length - 1;
        if (satisfaction[end] <= 0) {
            return 0;
        }
        int st = 0;
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            if (satisfaction[m] < 0) {
                st = m;
            } else {
                end = m - 1;
            }
        }
        int z = st + 1;
        int sum = 0;
        int value = 0;
        int index = 1;
        for (int i = z; i < length; i++) {
            int val = satisfaction[i];
            sum += val;
            value += val * index;
            index++;
        }
        for (int i = z - 1; i >= 0; i--) {
            sum += satisfaction[i];

            if (sum <= 0) {
                return value;
            }
            value += sum;
        }
        return value;
    }


}
